package src.leetcode.backtrack.hard_0051;

import javax.crypto.interfaces.PBEKey;
import java.util.*;
import java.util.zip.DataFormatException;

public class solveNQueens {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println("solution.solveNQueens(4) = " + solution.solveNQueens(4));
    }
}


class Solution {
    List<List<String>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int col = 0;
    int di1 = 0;
    int di2 = 0;
    int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        dfs(0);
        return res;
    }

    private void dfs(int c){
        if(path.size() == n) addpath();
        for(int i = 0; i < n; i++){
            if((col & (1 << i)) != 0 || (di1 & (1 << (i + c))) != 0 || (di2 & (1 << (i - c + n))) != 0) continue;

            path.add(i);
            col += 1 << i;
            di1 += 1 << (i + c);
            di2 += 1 << (i - c + n);

            dfs(c + 1);

            path.remove(path.size() - 1);
            col -= 1 << i;
            di1 -= 1 << (i + c);
            di2 -= 1 << (i - c + n);
        }
    }

    private void addpath(){
        List<String> board = new ArrayList<>();
        for(int i = 0; i < n; i++){
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[path.get(i)] = 'Q';
            board.add(new String(row));
        }
        res.add(board);
    }
}



//class Solution {
//    List<List<String>> res = new ArrayList<>();
//    List<Integer> path = new ArrayList<>();
//    Set<Integer> col = new HashSet<>();
//    Set<Integer> di1 = new HashSet<>();
//    Set<Integer> di2 = new HashSet<>();
//    int n;
//
//    public List<List<String>> solveNQueens(int n) {
//        this.n = n;
//        dfs(0);
//        return res;
//    }
//
//    private void dfs(int c){
//        if(path.size() == n) addpath();
//        for(int i = 0; i < n; i++){
//            if(col.contains(i) || di1.contains(i + c) || di2.contains(i - c)) continue;
//
//            col.add(i);
//            di1.add(i + c);
//            di2.add(i - c);
//            path.add(i);
//
//            dfs(c + 1);
//
//            col.remove(i);
//            di1.remove(i + c);
//            di2.remove(i - c);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    private void addpath(){
//        List<String> board = new ArrayList<>();
//        for(int i = 0; i < n; i++){
//            char[] row = new char[n];
//            Arrays.fill(row, '.');
//            row[path.get(i)] = 'Q';
//            board.add(new String(row));
//        }
//        res.add(board);
//    }
//}